﻿#pragma once
#include "stdafx.h"

/*
删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题想法：拿到题目后，我想到了，要是这个链表有个数组下标，总数知道了，位置知道了，
是不是想删除那个就非常方便了，这个方案在数据结构中的间接寻址，可以使用vector 方式使用
把对应指针记录下来，便可以解决，时间复杂度O(n),空间复杂度O(n),在题目中是空间不够
 如果,想要空间复杂度小一点，可以使用3个指针，初始化第一个l指针为第一个，第二r为第二个，
 第三个为e与第一个差距为n的指针位置，然后共同移动，知道最后一个e指到最后一个，那么r就是需要
 删除的对象。l就是前一个指针，这样数据结构 时间复杂度O(n),空间复杂度O(1)
*/

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
	
};
//方案1  使用vector<ListNode*>
ListNode* removeNthFromEnd(ListNode* head, int n) 
{
	vector<ListNode*> pList;
	
	ListNode* current = head; //当前指向的指针
	while (current)
	{
		pList.push_back(current);
		current->next;
	}

	//判断pList的长度
	int length = pList.size();
	//要删除的下标位置
	int index = length - n;
	if (index == 0) //当为头的时候
	{
		current = head;
		head = head->next;
		delete current;
	}
	else  //当不为头的时候
	{
		int proIndex = index - 1; //前一个位置
		current = pList[index];
		pList[proIndex]->next = pList[index]->next;
		delete current;
	}
	return head;
	
}


//方案2 采用三个指针方式，简称就是双指针法。由于n是合理的，题目说了
ListNode* removeNthFromEnd2(ListNode* head, int n)
{
	ListNode* L = head;
	ListNode* R = L->next;
	ListNode* End = L;
	int length = 1;
	if (!R && L) //这个时候有只有头
	{
		head = head->next;
		return head;
	}
	for (int i = 0; i<n; i++)
	{
		if (End->next)
		{
			End = End->next;
			length++;
		}
		
	}
	//初始化后，开始共同移动
	while (End->next)
	{
		End = End->next;
		R = R->next;
		L = L->next;
		length++;
	}
	//这个时候End移动到了最后的位置了，可以删除R的数据了。
	if (length == n)//删除是表头
	{
		head = head->next;
	}
	else
	{
		L->next = R->next;
	}
	return head;
}

